/************************ AGREEMENT ****************************\
Author : Liwen Chu
Email : hiensjtu@gmail.com
Comment: Feel free to use any part of this file, however, keeping
of the author infomation would be appreciated.
\***************************************************************/

#include "stdafx.h"
#include "BST.h"
#include <iostream>

using namespace std;

BST::BST(int nList[], int nLength):m_root(0)
{
	if(nLength > 0)
	{
		m_root = new node();
		m_root->data = nList[0];
		m_root->pLeft = m_root->pRight = 0;

		for(int i = 1; i < nLength; ++i)
		{
			Insert(nList[i], m_root);
		}
	}
}

BST::~BST()
{
	Remove(m_root);	
}

void BST::Remove(node *p)
{
	if(p->pLeft)
	{
		Remove(p->pLeft);
	}
	
	if(p->pRight)
	{
		Remove(p->pRight);
	}
	delete p;
}

void BST::Insert(int data, node *root)
{
	if(data < root->data)
	{
		if(root->pLeft)
		{
			this->Insert(data, root->pLeft);
		}
		else
		{
			node *pNode = new node();
			pNode->data = data;
			root->pLeft = pNode;
		}
	}
	else
	{
		if(root->pRight)
		{
			Insert(data, root->pRight);
		}
		else
		{
			node *pNode = new node();
			pNode->data = data;
			root->pRight = pNode;
		}		
	}
}

void BST::PreOrderTraverse(node *root)
{
	if(root)
	{
		(*visit)(root);
		PreOrderTraverse(root->pLeft);
		PreOrderTraverse(root->pRight);
	}
}

void BST::InOrderTraverse(node *root)
{
	if(root)
	{
		InOrderTraverse(root->pLeft);
		visit(root);
		InOrderTraverse(root->pRight);
	}
}

void BST::PostOrderTraverse(node *root)
{
	if(root)
	{
		PostOrderTraverse(root->pLeft);
		PostOrderTraverse(root->pRight);
		(*visit)(root);
	}
}